import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-05-23
 * Time: 19:52
 */

/*
* 时间复杂度：1+2+........+n-1=n^2
* 最好的情况： n
* 最坏的情况 n^2
* 空间复杂度：o（1）//没有因为排序再重新申请一个数组
* 稳定性：包稳定的（稳定的可以变得不稳定，但是不稳定的肯定不能变得稳定）
* */
public class Sort {


    public static void inSertSort(int[] array){
        for (int i = 1 ; i < array.length ; i++){
            int tem = array[i];//tem这个变量是用来存储需要被比较的哪个值，即擂主，让i下标后面的的值挨个跟tem比
            int j = i-1 ;
            for (; j >= 0 ; j--){
                if(array[j] > tem ){ //如果加 = 那么排序会变得不稳定
                    array[j+1] = array[j];
                }else {
                    break; // array[j+1] = tem; 但是跳出循环后已经有赋值了就不必再写一次了
                }
            }
            array[j+1] = tem;
        }
    }
    public static void inSertSort(int[] array,int left,int right){//构成重载关系
        for (int i = left+1 ; i <= right ; i++){//区间范围都是闭区间，包含left和right
            int tem = array[i];//tem这个变量是用来存储需要被比较的哪个值，即擂主，让i下标后面的的值挨个跟tem比
            int j = i-1 ;
            for (; j >= left ; j--){
                if(array[j] > tem ){
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tem;
        }
    }
    /*
    * 希尔排序越排越有序
    * 分组*/
    public  static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            gap /= 2;
            shell(array , gap);//插入排序
        }
    }
    public static void shell(int[] array , int gap){
        for (int i = gap ; i < array.length ; i++){//这里的i++是一个重点，交替排序比较   //int i = gap +1  结果也是一样的这个开始的顺序问题不大
            int tem = array[i];   //重点：gap代表的意思是分的组数。比如10个数据分两组那下标
            int j = i-gap;
            for (; j >= 0 ; j-=gap){
                if(array[j] > tem ){ //如果加 = 那么排序会变得不稳定
                    array[j+gap] = array[j];
                }else {
                    break; // array[j+1] = tem; 但是跳出循环后已经有赋值了就不必再写一次了
                }//这里的break是跳出当前for循环，然后54行又赋值回去了
            }
            array[j+gap] = tem;
        }
    }
    public static void swap(int[]array , int i , int j){
        int tem = array[i];
        array[i] = array[j];
        array[j] = tem;
    }
    /*
    * 时间复杂度：O(N^2)
    * 空间复杂度:1
    * */
    public static void selectSort(int[] array){
        for (int i = 0 ; i < array.length ; i++){
            int minIndex = i; //这里定义的minIndex是为了让数据一个一个往后排
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < array[minIndex]){ //array[j] < array[i]是错的,minIndex是在不断变化的，所以跟minIndex去比较
                    minIndex = j;//这里是记录在当前i这个循环下元素的最小值的下标
                }
            }
            swap(array,minIndex,i);
        }
    }
    public static void selectSort2(int[] array){
        int left = 0;
        int right = array.length-1;
        while (left < right) {//直到两者相遇
            int minIndex = left;
            int maxIndex = left;//
            for (int i = left + 1; i <= right; i++) { //注意一下i要一直走完整个数组，所以取需要取=号
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array, left, minIndex);
            if(maxIndex == left){
                maxIndex = minIndex;//防止新的最大值下标已经被交换到最小值下标处了，所以更新一下最大值下标
            }
            swap(array, right, maxIndex);
            left++;
            right--;
        }
    }
    public static void creatHeap(int[] array){//创建大根堆
        for (int parent = ( (array.length-1)-1 )/2 ; parent >=0 ; parent-- ){
            shifDown(array, parent , array.length);
        }
    }//写完脑子要炸掉了
    public static void shifDown(int[] array ,int parent , int length){
        int child = 2*parent +1 ; //左孩子
        while (child < length){
            if (child + 1 < length && array[child] < array[child+1]) {//child + 1 < array.length 是错的，是需要调整的长度，不是数组的长度，代表的意义都不一样
                child = child +1;
            } //这里已经获得了孩子中最大值的那个孩子的下标
            if (array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

    public static void heapSort(int[] array){
        creatHeap(array);
        int end = array.length - 1;
        while (end >= 0){
            swap(array,0,end);
            shifDown(array,0,end);
            end--;//我已经要裂开了，还好之前堆的笔记做的好
        }
    }

    public static void bubbleSort(int[] array){
        for (int i = 0 ; i < array.length-1; i++){ //5个数据走4趟  , i是比较的次数
            boolean flag = false; //数据在处理的过程中可能i不用全部走完就排好序了
            for (int j = 0 ; j < array.length-1-i ; j++ ){ //j从哪里开始比较，到哪里结束，
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);//到这一步大体冒泡排序的框架就组织好了
                    flag = true;            //说明进行交换了
                }                             //
            }
            if(flag == false){  //if（！flag）//等价的 若flag=false   非flag = 1 进入循环
                break;
            }
        }
    }

    public static int middleNum(int[] array , int left , int right){
        /*分两种情况讨论（148行和158行）
        * 在细分
        * 找中间值让二叉树的两边的跟的数量尽量平衡
        * 作用于quick*/
        int middle = (left + right)/2;
        if (array[left] < array[right]){
            if (array[middle] < array[left]){
                return left;
            }else if (array[middle] > array[right]){
                return right;
            }else {
                return middle;
            }
        }else{
            if (array[left] < array[middle]){
                return left;
            } else if (array[middle] < array[right]) {
                return right;
            }
            else{
                return middle;
            }
        }
    }
    /*
    * 快速排序
    * 时间复杂度O（NlogN）
    * 空间复杂度O（logN）
    * */
    public static void quickSort(int[] array ){//过程有问题的时候跑debug很清楚
        quick(array,0,array.length-1);//{6,1,2,7,9,7,4,5,10,8}这个例子很好中间的那个7女少
    }

    public static void quick(int[] array , int start , int end){
        if(start >= end){
            return;
        }
        System.out.println("start："+start+" "+"end："+end);
        if (end - start+1 <= 15){
            inSertSort(array,start,end);
            return;
        }
        /*
        * middle方法有助于减少树的高度，减少递归的次数，但不会减少开辟的内存空间*/
        int index = middleNum(array,start,end);//找到中间值的下标
        swap(array,start,index);//让中间值作为基准值，即根节点
       /* int pirot = partitionHoare(array,start,end);*/
        /*
        * 158行代码是Hoare的排序方式，与161行挖坑排序方法有异曲同工之处*/
        int pirot = partitionHole(array,start,end);
        quick(array,start,pirot-1);//递归左边
        quick(array,pirot+1,end);//递归右边

    }

    public static int partitionHoare(int[] array, int left , int right){
        int temp = array[left];
        int i = left;//这是一个基准值(下标)，用二叉树去理解
        while (right > left){
            /*
            * 如果先走左边，有可能会出现，181代码，把相遇的大的数据和temp交换了
            * 所以先走右边，遇到小的停下来*/
            while (right > left && array[right] >= temp){//注意点1等于号一定要有，不然会死循环，烫手山芋，用挖坑法举例
                right--;
            }
            while (right > left && array[left] <= temp){
                left++;
            }
            swap(array,left,right);//走走走，把后面小的数和前面大的数进行交换
        }//走完这个循环说明right和left相遇了
        swap(array,i,left);
        return left ;//这是left走到了pivot支点的地方
    }
/*
* 做题的时候快排优先用：挖坑排序去做题*/
    public static int partitionHole(int[] array , int left, int right){
        int temp = array[left];
        while(left < right){
           /* while (left < right && array[right] < temp){
            array[left]=array[right];
            right--;
            }*/   //这么写是错的看下面的代码就懂了,逻辑就不对
            while (left < right && array[right] >= temp){
                right--;
            }
            array[left]=array[right];
            while (left < right && array[left] <= temp){
                left++;
            }//直到找到一个比array[left]大的数才停止
            array[right] = array[left];
            array[left] = temp;//right和left相遇了，array[right] = temp 也对
        }
        return left;
    }
/*
* 快速排序的第三种方式
* 指针排序，*/
    public static int partion(int[] array , int left , int right){
        int prev = left;
        int curr = left+1;
        while (curr <= right){
            if (array[curr] < array[left] && array[++prev] != array[curr]) {
                swap(array,curr,prev);
            }
            curr++;
        }
        swap(array, prev, left);
        return prev;
    }
    /*
    * 快速排序的非递归方法，本质（栈的应用）*/
    public static void quickSortNor(int[] array){
        int start = 0;
        int end = array.length-1;
        Stack<Integer> stack = new Stack<>();
        int pivot = partitionHoare(array,start,end);
        if(pivot-1 > start){
            stack.push(start);
            stack.push(pivot-1);
        }//先看pivot左边是否有至少两个元素，如果只有一个元素了，那就说明有序了嘛
        if (pivot+1 < end){
            stack.push(pivot+1);
            stack.push(end);
        }//再看pivot右边是否有至少两个元素
        while (!stack.isEmpty()){
            int right = stack.pop();
            int left = stack.pop();
            /*下面的代码逻辑同while循环之前的代码*/
            pivot = partitionHoare(array,left,right);
            if(pivot-1 > start){
                stack.push(start);
                stack.push(pivot-1);
            }
            if (pivot+1 < end){
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }
}
